一、题目大意标签:动态归划https://leetcode.cn/problems/arithmetic-slices如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。给你一个整数数组nums，返回数组nums中所有为等差数组的子数组个数。子数组是数组中的一个连续序列。示例1：输入：nums=[1,2,3,4]输出：3解释：nums中有三个子等差数组：[1,2,3]、[2,3,4]和[1,2,3,4]自身。示例2：输入：nums=[1]输出：0提示：1-1000二、解题思路因为
一、题目大意标签:动态规划https://leetcode.cn/problems/house-robber你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。示例1：输入：[1,2,3,1]输出：4解释：偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。 偷窃到的最高金额=1+3=4。示例2：输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额
一、题目大意标签:动态规划https://leetcode.cn/problems/perfect-squares给你一个整数n，返回和为n的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16都是完全平方数，而3和11不是。示例 1：输入：n=12输出：3解释：12=4+4+4示例2：输入：n=13输出：2解释：13=4+9提示：1二、解题思路动态规划，dp[i]表示i有几个完全平方数的加和构成，枚举比i小的完全平方数，状态转移方程为dp[i]=min(dp[i-k]+1)，k就是完全平方数三、解题方法3.1Java
一、题目大意标签:动态规划https://leetcode.cn/problems/maximal-square在一个由'0'和'1'组成的二维矩阵内，找到只包含'1'的最大正方形，并返回其面积。示例1：输入：matrix=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：4示例2：输入：matrix=[["0","1"],["1","0"]]输出：1示例3：输入：matrix=[["0"]]输出：0提示：m==matrix.lengthn==matrix[i]
一、题目大意标签:动态规划https://leetcode.cn/problems/01-matrix给定一个由0和1组成的矩阵mat ，请输出一个大小相同的矩阵，其中每一个格子是mat中对应位置元素到最近的0的距离。两个相邻元素间的距离为1。示例1：输入：mat=[[0,0,0],[0,1,0],[0,0,0]]输出：[[0,0,0],[0,1,0],[0,0,0]]示例2：输入：mat=[[0,0,0],[0,1,0],[1,1,1]]输出：[[0,0,0],[0,1,0],[1,2,1]]提示：m==mat.lengthn==mat[i].length11mat[i][j]iseithe
一、题目大意标签:动态规划https://leetcode.cn/problems/minimum-path-sum给定一个包含非负整数的m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。示例1：输入：grid=[[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径1→3→1→1→1的总和最小。示例2：输入：grid=[[1,2,3],[4,5,6]]输出：12提示：m==grid.lengthn==grid[i].length10二、解题思路二维的动态规则，定义一个二维dp数组，其中dp[i][j]
一、题目大意标签:动态归划https://leetcode.cn/problems/arithmetic-slices如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。给你一个整数数组nums，返回数组nums中所有为等差数组的子数组个数。子数组是数组中的一个连续序列。示例1：输入：nums=[1,2,3,4]输出：3解释：nums中有三个子等差数组：[1,2,3]、[2,3,4]和[1,2,3,4]自身。示例2：输入：nums=[1]输出：0提示：1-1000二、解题思路因为
一、题目大意标签:动态规划https://leetcode.cn/problems/house-robber你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。示例1：输入：[1,2,3,1]输出：4解释：偷窃1号房屋(金额=1)，然后偷窃3号房屋(金额=3)。 偷窃到的最高金额=1+3=4。示例2：输入：[2,7,9,3,1]输出：12解释：偷窃1号房屋(金额
1.题目给你一个正整数数组 nums ，对 nums 所有元素求积之后，找出并返回乘积中 不同质因数 的数目。注意：质数 是指大于 1 且仅能被 1 及自身整除的数字。如果 val2/val1 是一个整数，则整数 val1 是另一个整数 val2 的一个因数。 示例1：输入：nums=[2,4,3,7,10,6]输出：4解释：nums中所有元素的乘积是：2*4*3*7*10*6=10080=25*32*5*7。共有4个不同的质因数，所以返回4。示例2：输入：nums=[2,4,8,16]输出：1解释：nums中所有元素的乘积是：2*4*8*16=1024=210。共有1个不同的质因数，所以返回
初识动态规划，我对这个算法的理解是这样的：1.找到初始值-原始解2.在找到各种解与原始解的关系3.通过循环得到答案 适用于动态规划的问题首先就是不同路径：问题是给定一个M*N的地图从左上到右下角一共有多少种不同的方案（每次只能向右或者向下走一格）。那么解决这个问题的关键在于你如何确定初始解与答案之间的联系。首先我们可以确定地图的左边与上边都为1，因为只能往右或者下走。例如从【0，0】走到【0，5】只能选择连续向右走五步，或者从【0，0】走到【5，0】只能选择连续向下走五步。那么走到【1，1】有多少种走法？根据每次只能向下走一步或者向右走一步的特性，所以只能由【0，1】或者【1，0】到达【1，1
